package net.lainiao.leetcode;

import net.lainiao.leetcode.base.DirectedGraphNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

/**
 * Created by Administrator on 2018/1/21.
 */
public class LintCode127 {
//    拓扑排序
    public static void main(String[] args) {

    }

    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> result=new ArrayList<>();
        if(graph==null||graph.size()==0){
            return result;
        }

        HashMap<DirectedGraphNode,Integer> hashMap=new HashMap<>();
        Stack<DirectedGraphNode> stack=new Stack<>();

        for(DirectedGraphNode node:graph){
            hashMap.put(node,0);
        }

        for(DirectedGraphNode node:graph){
            for (DirectedGraphNode inNode:node.neighbors){
               hashMap.put(inNode,hashMap.get(inNode)+1);
            }
        }

        for(DirectedGraphNode node:graph){
            if(hashMap.get(node)==0){
                stack.push(node);
            }
        }

        while(!stack.isEmpty()){
            DirectedGraphNode current=stack.pop();
            result.add(current);
            for(DirectedGraphNode inNode:current.neighbors){
                int value=hashMap.get(inNode);
                value--;
                hashMap.put(inNode,value);
                if(value==0){
                    stack.push(inNode);
                }
            }
        }

        return result;
    }

}
